#include <unordered_map>

using namespace std;


/**
 * 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
 * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
 * https://leetcode.cn/problems/longest-palindrome/
 */
class Solution {
public:
    // 所有偶数个数都可以加入
    // 最长的奇数个数可以加入，其余奇数个数减去一再加入
    int longestPalindrome(string s) {
        unordered_map<char, int> table;
        for (char c : s) table[c]++;

        int even = 0;
        int max_odd = 0;
        for (auto& [c, cnt] : table) {
            if (cnt % 2 == 1) {
                if (cnt > max_odd) {
                    even += max(0, max_odd-1);
                    max_odd = cnt;
                } else even += (cnt-1);
            } else even += cnt;
        }
        return even + max_odd;
    }
};
